/*
STL 常用排序算法
算法简介
  sort  // 对容器内的元素进行排序
  random_shuffle  // 洗牌 指定范围内的元素随机调整次序
  merge  // 容器元素合并，并存储到另一容器中
  reverse  // 反转指定范围的元素

sort
  对容器内的元素进行排序
  函数原型
    sort(iterator beg, iterator end, _Perd);  _Pred 函数或谓词

random_shuffle
  洗牌 指定范围内元素随机调整次序 c++ 17中移除了改函数 用shuffle代替
  函数原型
    random_shuffle(iterator beg, iterator end);

merge
  合并两个容器元素并存储到另一个容器中, 如果v1, v2是有序的，会按所有元素从小到大排序到目标容器中，如果无需会先写小的在写大的
  函数原型
    merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

reverse
  翻转容器内的元素
  函数原型
    reverse(iterator beg, iterator end);
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;

void print(int v)
{
    cout << v << " ";
}
// sort
void test_sort()
{
    cout << "--------------- sort ------------------" << endl;
    vector<int> v = {3,5,0,8,2,4};
    sort(v.begin(), v.end());  // 默认从小到大排序
    cout << "default sort -> ";
    for_each(v.begin(), v.end(), print);
    cout << endl;

    sort(v.begin(), v.end(), greater<int>());  // 从大到小排序
    cout << "use greater sort -> ";
    for_each(v.begin(), v.end(), print);
    cout << endl;
}

// random_shuffle
void test_random_shuffle()
{
    cout << "--------------- random_shuffle ------------------" << endl;
    vector<int> v = {1,2,3,4,5};
    cout << "before random shuffle -> ";
    for_each(v.begin(), v.end(), print);
    cout << endl;

    srand((unsigned int)time(NULL));  // 设置随机种子
    random_shuffle(v.begin(), v.end()); 
    cout << "after random shuffle -> ";
    for_each(v.begin(), v.end(), print);
    cout << endl;
}

// merge
void test_merge()
{
    cout << "--------------- merge ------------------" << endl;
    vector<int> v1 = {3,5,0,8};
    sort(v1.begin(), v1.end());
    cout << "v1 -> ";
    for_each(v1.begin(), v1.end(), print);
    cout << endl;

    vector<int> v2 = {4,3,2,6};
    sort(v2.begin(), v2.end());
    cout << "v2 -> ";
    for_each(v2.begin(), v2.end(), print);
    cout << endl;

    vector<int> v3;
    v3.resize(v1.size()+v2.size());
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    cout << "v3 -> ";
    for_each(v3.begin(), v3.end(), print);
    cout << endl;
}

// reverse
void test_reverse()
{
    cout << "--------------- reverse ------------------" << endl;
    vector<int> v = {1,2,3,4};
    cout << "v -> ";
    for_each(v.begin(), v.end(), print);
    cout << endl;

    reverse(v.begin(), v.end());
    cout << "reverse v -> ";
    for_each(v.begin(), v.end(), print);
    cout << endl;
}

int main()
{
    test_sort();
    test_random_shuffle();
    test_merge();
    test_reverse();
}